package com.example.Arithmetic.Lettcode;

import com.example.Arithmetic.Arithmetic.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 日期：2023/10/14
 * 时间：20:20
 * 描述：根据一个前序遍历和中序遍历序列构造一个二叉树
 */
public class E04Lettcode105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
//                前左
                int[] leftpre = Arrays.copyOfRange(preorder, 1, i + 1);
//                前右
                int[] rightpre = Arrays.copyOfRange(preorder, i + 1, preorder.length);
//                中左
                int[] leftin = Arrays.copyOfRange(inorder, 0, i);
//                中右
                int[] rightin = Arrays.copyOfRange(inorder, i + 1, inorder.length);

                root.left = buildTree(leftpre, leftin);
                root.right = buildTree(rightpre, rightin);
                break;
            }
        }
        return root;
    }

   static class Solution {
        int[] preorder;
        HashMap<Integer, Integer> dic = new HashMap<>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for (int i = 0; i < inorder.length; i++) {
                dic.put(inorder[i], i);
            }
            return recur(0, 0, inorder.length - 1);
        }

        TreeNode recur(int root, int left, int right) {
            if (left > right) {
                return null;                          // 递归终止
            }
            TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
            int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
            node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
            return node;                                           // 回溯返回根节点
        }
    }

    public static void main(String[] args) {
        E04Lettcode105.Solution s=new E04Lettcode105.Solution();
        int[] i=new int[]{3,9,20,15,7};
        int[] j=new int[]{9,3,15,20,7};
        TreeNode treeNode = s.buildTree(i, j);
        E06Lettcode103 e06Lettcode103=new E06Lettcode103();
        List<List<Integer>> list = e06Lettcode103.zigzagLevelOrder(treeNode);
        System.out.println(list);
    }


}

